import java.util.Arrays;

public class Demo1 {
    public static void main(String[] args) {
        int[]arr={88,1,35,16,9,5};
        int left=0;
        int right=arr.length-1;
        while (left<right){
            int maxIndex=left;
            int minIndex=left;
            for (int i = left+1; i <=right ; i++) {
                if(arr[i]<arr[minIndex]){
                    minIndex=i;
                }
                if(arr[i]>arr[maxIndex]){
                    maxIndex=i;
                }
            }
            swap(arr,left,minIndex);
            if(maxIndex==left){
                maxIndex=minIndex;
            }
            swap(arr,right,maxIndex);
            left++;
            right--;
        }
        System.out.println(Arrays.toString(arr));
    }
    public static void main1(String[] args) {
        int[]arr={8,1,35,16,9,5};
        for (int i = 0; i <arr.length ; i++) {
            int midIndex=i;
            for (int j = i+1; j <arr.length; j++) {
                if(arr[j]<arr[midIndex]){
                    midIndex=j;
                }
            }
            swap(arr,i,midIndex);
        }
        System.out.println(Arrays.toString(arr));
    }

    public static void swap(int[]arr,int i,int j){
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }


        public void bubbleSort(int[] arr){
            for (int i = 0; i <arr.length ; i++) {
                boolean flg=false;
                for (int j = 0; j <arr.length-1-i ; j++) {
                    if(arr[j]>arr[j+1]){
                        swap(arr,j,j+1);
                        flg=true;
                    }
                }
                if(!flg){
                    break;
                }
            }
        }



        public static void quickSort(int[]arr){
            quick(arr,0,arr.length-1);
        }

        private static void quick(int[]arr,int start,int end){
            if(start>=end){ //如果不加=号 当两者相遇则证明左树到了最底下,但是还得考虑右树此时的右树是pivot+1 会大于end的条件也要考虑进去
                return;
            }

            int pivot=partition(arr,start,end);
            quick(arr,start,pivot-1);
            quick(arr,pivot+1,end);
        }


    private static int partition(int[] arr, int left, int right) {
        int par=arr[left];
        int tmpLeft=left;
        while(left<right){
            while ((left<right&&arr[right]>=par)){
                right--;
            }

            while (left<right&&arr[left]<=par){
                left++;
            }
            swap(arr,left,right);
        }
        swap(arr,left,tmpLeft);
        return left;
    }
}
